package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月11日
*时间：下午5:53:45
*/
public class Q182 {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        if (A == null || A.length() <= k) {
            return "";
        }
        char c[] = A.toCharArray();
        int length = c.length;
        boolean b[] = new boolean[length];
        for (int i = 0; i < k; i++) {
            char first = '0' - 1;
            int firstPosition = -1;
            for (int j = 0; j < length; j++) {
                if (!b[j]) {
                    if (first == '0' - 1) {
                        first = c[j];
                        firstPosition = j;
                    } else {
                        if (c[j] >= first) {
                            first = c[j];
                            firstPosition = j;
                        } else {
                            b[firstPosition] = true;
                            break;
                        }
                    }
                }
            }
            b[firstPosition] = true;

        }
        String rs = "";
        for (int i = 0; i < length; i++) {
            if (!b[i]) {
                if (rs.length() > 0 || c[i] != '0') {
                    rs += c[i];
                }
            }
        }
        return rs;
    }

    @Test
    public void testA() {
        String A = "20541930";
        int k = 3;
        System.out.print(DeleteDigits(A, k));
    }
}
